class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        elif n == 1 or n == 2:
            return 1
        a, b, r = 1, 1, 0
        for i in range(n-2):
            r = a + b
            a, b = b, r
        else:
            return r%(int(1e9+7))
